#include <cstdio>
#include <cstring>

int s[ 11 ] = { 1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049 };
int n, m, f[ 59049 ][ 10 ], d[ 10 ][ 10 ], dig[ 59049 ][ 10 ];

int min( int a, int b ) { return ( a < b ) ?a: b; }

void init( )
{
    int i, j, u, v, w, t;
    for ( i = 0; i < n; i++ )
        for ( j = 0; j < n; j++ )
            d[ i ][ j ] = -1;
    for ( i = 0; i < m; i++ )
    {
        scanf("%d%d%d", &u, &v, &w); u--; v--;
        if ( d[ u ][ v ] == -1 || d[ u ][ v ] > w )
            d[ u ][ v ] = d[ v ][ u ] = w;
    }
    for ( i = 0; i < s[ 10 ]; i++ )
    {
        t = i;
        for ( j = 0; j < 10; j++ )
        {
            dig[ i ][ j ] = t % 3;
            t /= 3;
        }
    }
}

int get( int a, int b )
{
    while ( b )
    {
        a /= 3;
        b--;
    }
    return a % 3;
}

void work( )
{
    int i, j, k, ans = 1000000000, t, flag;
    for ( i = 0; i < s[ n ]; i++ )
        for ( j = 0; j < n; j++ )
            f[ i ][ j ] = 1000000000;
    for ( i = 0; i < n; i++ )
        f[ s[ i ] ][ i ] = 0;
    for ( i = 0; i < s[ n ]; i++ )
    {
        flag = 1;
        for ( j = 0; j < n; j++ )
        {
            if ( dig[ i ][ j ] == 0 ) flag = 0;
            if ( f[ i ][ j ] == 1000000000 ) continue;
            for ( k = 0; k < n; k++ )
            {
                if ( j == k ) continue;
                if ( dig[ i ][ k ] >= 2 || d[ k ][ j ] == -1 ) continue;
                f[ i + s[ k ] ][ k ] = min( f[ i + s[ k ] ][ k ], f[ i ][ j ] + d[ j ][ k ] );
            }
        }
        if ( flag )
        {
            for ( j = 0; j < n; j++ )
                if ( ans > f[ i ][ j ] )
                    ans = f[ i ][ j ];
        }
    }
    if ( ans >= 1000000000 )
        puts("-1");
    else
        printf("%d\n", ans);
}

int main( )
{
    while ( scanf("%d%d", &n, &m) != EOF )
    {
        init( );
        work( );
    }
    return 0;
}
